package 多维动态规划;

/**
 * @author TTDB
 * @create 2025/9/26
 */
public class longestPalindrome {
    public String longestPalindrome(String s) {
        int n = s.length();
        if(n == 0) return "";
        int len = 1;
        int max = 0;
        int maxStart = 0;
        for(int i = 0; i < n; i++){
            //中心扩散,找到可扩散的点，在扩散
            int l = i - 1, r = i + 1;
            //先来看奇数--注意条件
            while(l >= 0 && s.charAt(l) == s.charAt(i)){
                len++;
                l--;
            }
            while(r < n && s.charAt(r) == s.charAt(i)){
                len++;
                r++;
            }
            while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                l--;
                r++;
                len += 2;
            }
            if(len > max){
                max = len;
                maxStart = l;
            }
            len = 1;
        }
        //substring(start, end),不包括end
        return s.substring(maxStart + 1, maxStart + max + 1);
    }
}
